package com.ls.sort_algorithm;

import java.util.Arrays;
import java.util.Date;

/**
 * 希尔排序
 * 第一次分为length/2组 每组两个（n组就是n步长，每n个步长的元素为一组）
 * 第二次分为(length/2)/2组
 * ...(组数逐渐减小)
 * 直到length/2ⁿ == 0 结束（无组可分,只有一组，步长为0）
 * 每组以插入排序进行排序
 * <p>
 * -----------------------------------
 * 每隔length/2ⁿ步,算一组,每组进行插入排序
 */
public class ShellSort {
    public static void main(String[] args) {

        ShellSort shellSort = new ShellSort();
        int[] arr = {3, 7, 9, -1, 11, 16, -2, 10, 5, 1};

//        int[] arr = new int[800000];
//        for (int i = 0; i < 800000; i++) {
//            arr[i] = (int) (Math.random() * 8000000);
//        }

        System.out.println(new Date());
        shellSort.shellSort3(arr);
        System.out.println(new Date());
    }

    /**
     * 交换法（希尔+冒泡）
     * gap 步长
     *
     * @param arr
     */
    public void shellSort(int[] arr) {

        int temp = 0;
        for (int gap = arr.length / 2; gap > 0; gap /= 2) {
            for (int i = gap; i < arr.length; i++) {
                //遍历每一组中所有的元素(共gap组,每组有)
                for (int j = i - gap; j >= 0; j -= gap) {
                    if (arr[j] > arr[j + gap]) {
                        temp = arr[j];
                        arr[j] = arr[j + gap];
                        arr[j + gap] = temp;
                    }

                }

            }
        }
        System.out.println(Arrays.toString(arr));
    }


    /**
     * 移动法（希尔+插入）
     * gap 步长:当成插入排序里面的1
     *
     * @param arr
     */
    public void shellSort2(int[] arr) {


        for (int gap = arr.length / 2; gap > 0; gap /= 2) {//gap= 5, 2, 1

            for (int i = gap; i < arr.length; i++) {

                int j = i - gap;//左面的索引
                int temp = arr[i];//右面的值
                while (j >= 0 && temp < arr[j]) {//如果右值<左值
                    arr[j + gap] = arr[j];
                    j -= gap;
                }
                arr[j + gap] = temp;

            }
        }


//        System.out.println(Arrays.toString(arr));
    }



    /*






























     */


    public void shellSort3(int[] arr) {


        for (int gap = arr.length / 2; gap > 0; gap /= 2) {
            for (int i = gap; i < arr.length; i++) {
                int temp = arr[i];
                int index = i - gap;
                while (index >= 0 && temp < arr[index]) {
                    arr[index +gap] = arr[index];
                    index -= gap;
                }
                arr[index +gap] = temp;
            }
        }


        System.out.println(Arrays.toString(arr));
    }


}
